package com.ly.algorithm.offerpointer;


import java.util.HashMap;

/**
 * @Classname Offer07
 * @Description
 *
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 *
 *  
 *
 * 例如，给出
 *
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 * 返回如下的二叉树：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *
 * @Date 2020/12/30 20:17
 * @Author 冷心影翼
 */
public class Offer07 {

    public static void main(String[] args) {
        Solution07 solution07 = new Solution07();
        TreeNode treeNode = solution07.buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
        treeNode.preOrder(treeNode);
    }

}

class Solution07 {

    private HashMap<Integer, Integer> hashMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        hashMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            hashMap.put(inorder[i],i);
        }
        return buildTree(preorder,0,0,inorder.length-1);
    }

    private TreeNode buildTree(int[] preorder,int root,int left,int right) {

        if(left>right) {
            return null;
        }
        TreeNode t = new TreeNode(preorder[root]);
        int i = hashMap.get(preorder[root]);
        t.left = buildTree(preorder,root+1,left,i-1);
        t.right = buildTree(preorder,i-left+root+1,i+1,right);
        return t;
    }


}